1. Technical Field of the Invention
The present invention relates to circuitry for carrying out a square root operation and a division operation.
2. Description of Related Art
When the division X/D is performed, a quotient Q and remainder R are determined which satisfy the following equation:X=Q.D+R where D>R>=0The remainder must be less than the divisor D, otherwise not enough subtractions of the divisor have been performed, but greater than or equal to zero otherwise too many subtractions of the divisor have been performed. Division can be performed using a succession of iterations. Effectively, in each iteration the divisor is subtracted from the remaining sum.
In restoring division the following steps are performed:                1. Ensure that X is less than D so that the resulting quotient is a fraction. This can be achieved by using normalization techniques;        2. Set R0=X so the entire dividend (that is the value to be divided and in this case X) becomes the initial remainder;        3. Shift Ri left 1 place, and subtract the divisor D. If Ri is negative then restore the value prior to subtraction and set qi to 0. qi is quotient bit i. Otherwise do not restore the value and set qi to 1; and        4. Perform n−1 iterations for an n-bit divisor X.The resulting quotient is Q=0.q1q2q3. . . qn−1.        
The iteration can be defined by the following formula:Ri=2Ri−1−q1D where i=1, 2, . . . n−1The problem with this method is the restoration of the previous result may be required on every step. The non-restoring algorithm is an alternative way of performing division and will perform the subtraction anyway and compensate for it on the next iteration if the resulting remainder is negative by adding the divisor instead. The decision whether to add the divisor on the next iteration is based on whether the remainder was either less than or greater than or equal to 0. The selection rule for determining each bit of the quotient is as follows:qi=1 if 2Ri−1>=0 andqi=−1 if 2Ri−1<0.Each bit of the quotient represents either 1 or −1. In the resulting word −1 is represented by bit 0 and +1 by bit 1. This requires conversion to a standard binary number. Thus, to convert the quotient 0.q1q2. . . qm−1 into the two's complement representation S0.S1.S2. . . Sn−1 the following holds:s0. S1. S2. . . Sm= q1q2q3. . . qm1.In other words, the top bit is complemented, the word is shifted left one place and the least significant bit is set to one.
The SRT (Sweeney, Robertson and Tocher) division algorithm is an extension of non-restoring division. In each iteration, an addition, a subtraction or nothing is performed. The decision is taken based on the value of the current remainder. The current partial remainder can be approximated by referring only to a few of the most significant bits and a suitable quotient digit assigned. The selection rule is as follows:qi=1 if 2Ri−1>=Dqi=0 if −D<=2Ri−1<Dqi=−1 if −D>2Ri−1.The range of the divisor can be restricted to make the decision making process simpler by allowing the range:½<=|D|<1.This means that the selection rule can be implemented as follows:qi=1 if 2Ri−1>=½qi=0 if −½<=2Ri−1<½qi=−1 if −½>2Ri−1.As the comparison operations are only less than ½ or greater than or equal to ½, the examination of the lower or least significant bits is never required, only the sign bit down to one bit to the right of the binary point needs to be examined. In other words, only three bits in total need to be considered. The selected quotient bits are represented by three values −1, 0 and 1.
Square root determination uses a similar algorithm to division. In particular, the following is evaluated:Ri=2Ri−1−qi(2Qi−1−qi2−1) where i=1, 2, . . . n−1Thus, the value used to modify the result is a function of the previous quotient Qi−1 as well as the currently determined bit qi. The simple selection rule is similar to that used for division and is as follows:qi=1 if ½<=2R<=2qi=0 if −½<=2Ri−1<½.qi=−1 if −2<=>2Ri−1<½.
Reference is made to FIG. 1 which shows a known arrangement for implementing a SRT division stage. The arrangement shown in FIG. 1 is to deal with a 53 bit number. Accordingly, a 55 bit carry save adder 10 is provided. The carry save adder 10 receives the remainder Ri−1 defined by its sum and carry parts and also a third input from a multiplexer 12. Depending on the output of the multiplexer, the divisor is added, subtracted or nothing is changed by the output of the multiplexer. The multiplexer 12 is controlled by the signal qi−1 representing that bit of the quotient.
The output of the carry save adder is signal Ri again defined by its sum and carry parts. The three most significant bits of the sum and carry parts of the remainder output by the carry save adder 10 are input to a three bit carry propagate adder 14 which sums the three most significant bits. The output of the carry propagate adder 14 is input to a quotient selection logic block 16. The quotient selection logic block 16 is arranged to implement the selection rule discussed previously so as to provide the value of qi. The quotient selection logic block 16 also receives the value qi−1 as an input.
The three bit carry propagate adder 14 is arranged to take the output from the carry save adder 10. Thus, for each iteration, two additions need to be performed, one by the carry save adder 10 and one by the carry propagate adder 14.